/*
STL map uses BST for search, O(log(n)), stable
Hash map, best O(1), worst O(n)
*/
#include <iostream>
#include <string>
#include <ext/hash_map>
#include <stack>
#include <jhy_aid.h>

using namespace std;
using namespace __gnu_cxx;
using namespace JHY;

// reverse the words order
    class Wmarks{
    public:
        int s, e;
        Wmarks(): s(-1), e(-1){;}
        Wmarks( const Wmarks& m ){ s=m.s; e=m.e; }
        void reset(){ s=-1; e=-1; }
        const int charNum()const{ return e-s+1; }
    };
void reverseSentence( string &str )
{    
    stack< Wmarks > marStack;
    Wmarks wm; // store each word's beginning and ending position
        
    // push words postion mark
    int strLen = str.length();
    //cout <<"orignial length: " << strLen <<endl;
    for(int i=0; i<strLen; i++)
    {
        // biginning pos mark
        if( str.at(i) != ' ' )
            if( wm.s == -1 )
                wm.s = i;  // beginning
        
        // ending pos mark
        if( str.at(i) == ' ' || i==(strLen-1) )
            if( wm.e == -1 && wm.s != -1 )
            {
                if( i==(strLen-1) )
                    wm.e = i;     // if at sentence end
                else
                    wm.e = i-1;   // ending
                marStack.push( wm ); // push marks into stack
                //cout << i << " : "<< wm.s << " , " << wm.e << endl;
                wm.reset(); // reset marks object
            }
    }
    
    // create new string 
    char bf[ strLen+1 ];
    int bi = 0; // buffer pos
    while( !marStack.empty() )
    {
        Wmarks se = marStack.top();
        int charNum = se.charNum();
        //cout << "copy "<< charNum <<" char" << endl;
        while( charNum )
        {
            //cout << "source char id: " << se.s <<endl;
            bf[ bi ] = str.at(se.s);
            bi ++;
            se.s ++;
            charNum --;
        }
        if( bi< strLen )
        {
            bf[ bi ] = ' '; // insert space
            bi ++;            
        }

        marStack.pop(); // pop word's marks
    }
    bf[ strLen+1 ] = '\0';
    
    str = string( bf ); // update result
}

char firstNonRepeated( const string & str )
{
    hash_map<char, int> hmap;
    
    int length = str.length();
    char c;
    
    // scan str to build hash table
    for(int i=0; i<length; i++)
    {
        c = str.at(i);
        if( hmap.find( c )!= hmap.end() )
        {
            hmap[c] ++; 
        }else{
            hmap[c] = 1;
        }
    }
    
    // search the character counter in order of string
    for(int i=0; i<length; i++)
    {
        c = str.at(i);
        if( hmap[c]==1 )
        {
            return c;
        }
    }    
    
    return NULL;
}

// if want to change the pointer's buffer, the input argument have to be
// pointer's pointer **
void removeChar( char **source, const int sn, char *remove, const int rn )
{
    // set hash table for removing list
    hash_map<char, bool> hm_rm;
    for (int i=0; i<rn; i++)
    {
        char c = remove[i];
        hm_rm[c] = true;
    }       
    
    int cpNum = sn - rn;
    char *newbf = new char[cpNum];
    int ii=0; // new buffer id
    for(int i=0; i<sn; i++)
    {
        char c = (*source)[i];
        if( hm_rm[c]==false )
        {
            newbf[ii] = c;
            ii++;
        }
    }
    newbf[ii] = '\0';
    
    delete [] *source; // the source buffer has to be created by new []
    *source = newbf;
}

int main()
{    
    string line = "Stack Overflow is a question and answer site for professional and enthusiast programmers";
    cout << "original: " << endl << "\t " << line << endl;
    reverseSentence( line );
    cout << "result: " << endl << "\t" << line << endl;
    exit(0);

    // remove char from string
    char source[] = "it is a good day for fun!";
    char remove[] = "good";
    const int sn = sizeof(source)/sizeof(char);
    const int rn = sizeof(remove)/sizeof(char);    
    cout <<"sn: "<< sn <<" ,rn: " << rn << endl;
    
    char *sbf = new char[sn];
    strcpy( sbf, source );
    cout << "source: "<< sbf <<" ,remove: " << remove << endl;
    removeChar( &sbf, sn, remove, rn );
    cout << "result: " << sbf << endl;
    
    exit(0);
    
    // find first non repeated char
    string tmp = "aaa bb eeeeee f";
    cout << firstNonRepeated( tmp ) << endl;
    
    // ----------------------    
    // GNU hash_map test
    // ----------------------
    hash_map<char, int> hm;
    hm['a']=100;
    hm['b']=200;
    hm['c']=300;
    
    hash_map<char, bool> hmm;
    hmm['b'] = true;
    cout<<"test hash: " << hmm['d'] <<" , " << hmm['b'] << endl;
    exit(0);
    
    hash_map<char, int>::iterator last;
    last = hm.begin();
    last ++;
    cout <<"iterator: " << hm.begin()->second <<" , " << last->second << endl;
    
}
